package jianzhiOffer;

import java.util.ArrayList;
import java.util.Stack;

/**
 * @author : xwj
 * @date : 2021/9/27 22:29
 * @description : 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，
 *                调用 min、push 及 pop 的时间复杂度都是 O(1)。
 * @class : test02
 **/

public class test02 {

    //使用一个ArrayList来模拟栈
    static class MinStack {

        ArrayList<Integer> s;

        /** initialize your data structure here. */
        public MinStack() {
            s = new ArrayList<>();
        }

        public void push(int x) {
            s.add(x);
        }

        public void pop() {
            s.remove(s.size() - 1);
        }

        public int top() {
            return s.get(s.size() - 1);
        }

        public int min() {
            int min = s.get(0);
            for (int i = 1; i < s.size(); i++) {
                if (min > s.get(i)) {
                    min = s.get(i);
                }
            }
            return min;
        }
    }

    //使用两个栈来实现
    //一个栈用来保存栈中的数，一个栈用例保存最小值
    static class MinStack2 {

        Stack<Integer> s1;
        Stack<Integer> s2;

        /** initialize your data structure here. */
        public MinStack2() {
            s1 = new Stack<>();
            s2 = new Stack<>();
        }

        public void push(int x) {
            s1.push(x);
            if (s2.isEmpty() || s2.peek() >= x) {
                s2.push(x);
            }
        }

        public void pop() {
            if (s1.pop().equals(s2.peek())) {
                s2.pop();
            }
        }

        public int top() {
            return s1.peek();
        }

        public int min() {
            return s2.peek();
        }
    }

    //自己实现栈
    static class MinStack3 {

        class Node {
            int val;
            Node next;
            Node pre;

            Node() {}
            Node(int n) {this.val = n;}
            Node(int n, Node pre) {this.val = n; this.pre = pre;}
            Node(int n, Node next, Node pre) {this.val = n; this.next = next; this.pre = pre;}
        }

        Node n1;
        Node n2;

        /** initialize your data structure here. */
        public MinStack3() {
            n1 = new Node();
            n2 = new Node();
        }

        public void push(int x) {
            Node n = new Node(x, n1);
            n1.next = n;
            n1 = n1.next;
            if (n2.pre == null || n2.val >= x) {
                n2.next = n;
                n2 = n2.next;
            }
        }

        public void pop() {
            if (n2.val >= n1.val) {
                n2 = n2.pre;
                n2.next = null;
            }
            n1 = n1.pre;
            n1.next = null;
        }

        public int top() {
            return n1.val;
        }

        public int min() {
            return n2.val;
        }

    }

    public static void main(String[] args) {
        MinStack3 minStack = new MinStack3();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println(minStack.min());
        minStack.pop();
        System.out.println(minStack.top());
        System.out.println(minStack.min());
    }

}
